package com.ljy.my_study.lintcode.最大的树;

/**
 * @author James
 * @date 2019年5月8日
 */
public class TestMain {
	// Given an integer array with no duplicates. A max tree building on this array
	// is defined as follow:
	//
	// The root is the maximum number in the array
	// The left subtree and right subtree are the max trees of the subarray divided
	// by the root number.
	// Construct the max tree by the given array.
	// Have you met this question in a real interview? Yes
	// Problem Correction
	// Example
	// Example 1:
	//
	// Input：[2, 5, 6, 0, 3, 1]
	// Output：{6,5,3,2,#,0,1}
	// Explanation：
	// the max tree constructed by this array is:
	// 6
	// / \
	// 5 3
	// / / \
	// 2 0 1
	// Example 2:
	//
	// Input：[6,4,20]
	// Output：{20,6,#,#,4}
	// Explanation：
	// 20
	// /
	// 6
	// \
	// 4
	//
	// Challenge
	// O(n) time and memory.
	public static void main(String[] args) {
		int[] A= {2, 5, 6, 0, 3, 1};
		TreeNode top=maxTree(A);
		System.out.println(top);
	}

//	需要按照数组顺序
	public static TreeNode maxTree(int[] A) {
		TreeNode top=null;
		for(int a:A) {
			if(top==null) {
				top=new TreeNode(a);
				continue;
			}
			top=changeTree(top,a);
		}
		return top;
	}
	
	public static TreeNode changeTree(TreeNode top,int nextVal) {
		int lastVal=top.val;
		if(lastVal>nextVal) {
			if(top.right==null) {
				top.right=new TreeNode(nextVal);
			}else {
				top.right=changeTree(top.right,nextVal);
			}
			return top;
		}else {
			TreeNode newTop=new TreeNode(nextVal);
			newTop.left=top;
			return newTop;
		}
	}

	public static class TreeNode {
		public int val;
		public TreeNode left, right;

		public TreeNode(int val) {
			this.val = val;
			this.left = this.right = null;
		}

		@Override
		public String toString() {
			return "{\"val\":\"" + val + "\",\"left\":\"" + left + "\",\"right\":\"" + right + "\"} ";
		}
	}
}
